Cos'è pumping lemma?

Pumping Lemma

Il Pumping Lemma (lemma del pompaggio) è un teorema fondamentale nella teoria dei linguaggi formali. È utilizzato principalmente per dimostrare che un determinato linguaggio non è regolare. Non può essere usato per dimostrare che un linguaggio è regolare. Esistono versioni del Pumping Lemma per classi di linguaggi formali diverse, come i linguaggi context-free.

Idea di base:

Il Pumping Lemma sfrutta la natura "ripetitiva" di stringhe sufficientemente lunghe in un linguaggio regolare. Se un linguaggio è regolare, allora tutte le stringhe sufficientemente lunghe in quel linguaggio contengono una sottostringa che può essere "ripetuta" (pompare) un numero arbitrario di volte, mantenendo la stringa risultante ancora nel linguaggio. In altre parole, se una stringa w è abbastanza lunga, può essere suddivisa in tre parti, x, y, e z, tale che xyⁱz appartenga al linguaggio per ogni i ≥ 0, dove y non è vuota.

Pumping Lemma per Linguaggi Regolari (affermazione formale):

Sia L un linguaggio regolare. Allora esiste una costante p (la pumping length o lunghezza di pompaggio) tale che per ogni stringa w in L con |w| ≥ p, w può essere suddivisa in tre sottostringhe x, y, e z, tali che:

1. w = xyz
2. |y| > 0 (La sottostringa y non è vuota)
3. |xy| ≤ p (La lunghezza di xy è al massimo p)
4. Per ogni i ≥ 0, xyⁱz ∈ L (Pompare y un numero arbitrario di volte lascia la stringa nel linguaggio)

Utilizzo del Pumping Lemma per dimostrare che un linguaggio non è regolare:

Il Pumping Lemma viene usato per contraddizione. Per dimostrare che un linguaggio L non è regolare, è necessario:

1. Assumere che L sia regolare.
2. Usare il Pumping Lemma, quindi esiste una lunghezza di pompaggio p.
3. Trovare una stringa w ∈ L tale che |w| ≥ p.
4. Considerare tutte le possibili suddivisioni di w in x, y, e z che soddisfino le condizioni |y| > 0 e |xy| ≤ p.
5. Dimostrare che per ogni suddivisione possibile, esiste un valore di i ≥ 0 tale che xyⁱz ∉ L. Questo è il punto cruciale: si deve trovare un valore di i che "rompa" le regole del linguaggio L.
6. Se è possibile dimostrare che per tutte le suddivisioni esiste un i tale che xyⁱz ∉ L, allora si è trovata una contraddizione.
7. Pertanto, l'assunzione iniziale che L sia regolare è falsa, e quindi L non è regolare.

Esempio:

Considera il linguaggio L = {aⁿbⁿ | n ≥ 0}. Vogliamo dimostrare che questo linguaggio non è regolare usando il Pumping Lemma.

1. Assunzione: Assumiamo che L sia regolare.

2. Pumping Lemma: Sia p la lunghezza di pompaggio garantita dal Pumping Lemma.

3. Scelta di w: Sia w = a^pb^p. Chiaramente, w ∈ L e |w| = 2p ≥ p.

4. Suddivisioni: Consideriamo le possibili suddivisioni di w in x, y, e z tali che w = xyz, |y| > 0, e |xy| ≤ p. Poiché |xy| ≤ p, xy deve consistere interamente di simboli 'a'. Quindi possiamo scrivere:

   • x = a^j, dove 0 ≤ j < p
   • y = a^k, dove 0 < k ≤ p (perché |y| > 0)
   • z = a^p-j-kb^p

5. Pompaggio: Scegliamo i = 2. Allora xy²z = a^ja^2ka^p-j-kb^p = a^p+kb^p. Poiché k > 0, la stringa a^p+kb^p ha più 'a' che 'b' e quindi non appartiene a L.

6. Contraddizione: Abbiamo dimostrato che per ogni suddivisione possibile di w in x, y, e z, esiste un i (in questo caso i = 2) tale che xyⁱz ∉ L. Questo contraddice il Pumping Lemma.

7. Conclusione: Pertanto, l'assunzione che L sia regolare è falsa, e quindi L non è regolare.

Argomenti Importanti:

• Linguaggi Regolari: https://it.wikiwhat.page/kavramlar/Linguaggi%20Regolari
• Lunghezza di Pompaggio (Pumping Length): https://it.wikiwhat.page/kavramlar/Lunghezza%20di%20Pompaggio
• Dimostrazione per Contraddizione: https://it.wikiwhat.page/kavramlar/Dimostrazione%20per%20Contraddizione